The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
RFC 2827 describes the need to implement unicast reverse path forwarding(RPF) to prevent source address forging. FIG. 1A shows an example prior art router or switch having multiple line cards, each typically with multiple interfaces. Strict-mode reverse path forwarding requires that the source address of a packet received on an interface must be reachable from that interface.
For example, FIG. 1B illustrates two connected intranets, each having four routers. Denoted are two routers A and B, with router A having interfaces A-1 and A-2 connected to links to other routers as shown. If router B sends a packet to router A and if the packet is received on interface A-2, then the RPF condition is satisfied, and the packet is processed and forwarded. However, if the packet is received on interface A-1, then it is invalid as the routing reachability information will not include interface A-1 as there is a lower-cost path to reach node B in the network.
There are two known ways for performing the RPF checking. First, static access control lists (ACLs) can be manually created by an operator to specify the source addresses allowed on a particular interface. Major disadvantages of this approach include that different ACLs need to be manually defined for each interface, and these ACLs need to be manually updated to accommodate changes in the network topology to provide proper protection.
A second known approach is to perform two lookup operations on the forwarding information base (FIB): one based on the destination to identify a location which to forward the packet and a second lookup operation based on the source address of the packet to identify whether the packet was received on an allowed interface. This approach requires a second lookup operation on the FIB, which either decreases the rate at which packets can be forwarded (as it requires two lookups instead of just one) or it requires additional or duplicated components to perform these two lookup operations in parallel. Moreover, a third lookup operation is typically also performed, this one on a set of predefined ACLs to further identify how to process the packet. Performing all these lookup operations affects the rate at which packets can be processed and/or the amount of hardware and software required to perform such operations.
In one known approach, when unicast reverse path forwarding is enabled on an interface, the router examines all packets received on that interface. The router checks to make sure that the source address appears in the routing table and matches the interface on which the packet was received. This feature checks to see if any packet received at a router interface arrives on one of the best return paths to the source of the packet. The feature does this by doing a reverse lookup in the routing/forwarding information base based on the source address of the packet. If a corresponding reverse path for the packet is not located, this feature can drop or forward the packet, depending on whether an ACL is specified in a configuration command. If an ACL is specified in the command, then when (and only when) a packet fails the unicast reverse path forwarding check, the ACL is checked to see if the packet should be dropped (using a deny statement in the ACL) or forwarded (using a permit statement in the ACL). If no ACL is specified in the configuration command, the router drops the forged or malformed packet immediately.
Shown in FIG. 1C is a prior art data structure used specifying the RPF information for various source addresses. The data structure includes some information to perform a lookup operation on an address to identify a corresponding leaf node (i.e., a sub-data structure for the corresponding address, not limited to a tree type data structure, with the term “sub-data structure” intended to merely imply that it is reached via a lookup or other retrieval operation).
For example, there are an unlimited number of mechanisms for performing a lookup operation on an address to identify a leaf node, such as, but not limited to placing address in an associative memory, performing a direct or hashed lookup on the address or several strides of the address (i.e., MTRIE, etc.), tree bitmap (e.g., that disclosed in U.S. Pat. No. 6,560,610, issued May, 6, 2003, which is hereby incorporated by reference), compressed prefix matching database searching (e.g., that disclosed in U.S. Pat. No. 5,781,772, issued Jul. 14, 1998, which is hereby incorporated by reference), and an unlimited number of other lookup mechanisms and approaches.
As shown in FIG. 1C, each leaf node corresponding to a different address contained a bitmap indicating on which valid interface or interfaces a packet with the corresponding source address could be received. Thus, each address stored in the data structure (and for large routers this could be thousands or millions of addresses) contained its corresponding RPF information, and each of which must be maintained.
Identifying routing changes in a network is well-known. For example, a border gateway protocol (BGP) and interior gateway protocol (IGP) are commonly used to maintain routing information/network topology information about a network. BGP-4 is specified in RFC 1654, which is incorporated by reference. RIP is a commonly used IGP, and is specified in RFC 1058 and RFC 1723, which are both hereby incorporated by reference. Based on the BGP and IGP messages sent and received, each router maintains its routing database including reachability information (e.g., how to send a packet to reach its intended destination), and identifies changes in the reachability information.
FIG. 1D illustrates an update mechanism used to update each of these bitmaps for a particular routing change, which was associated with a linked list of pointers indicating the leaf nodes which must be updated for the particular update. A particular routing change to the route to reach a node may change a single one or even a large number (e.g., up to tens of thousands or even more) of RPF information as each bitmap has to be updated accordingly. Thus, in certain network configurations, a large number of updates must to be performed for a single change in reachability information (e.g. a change in the network topology). Such a mechanism has been used for a significant period of time as a better approach was desired, but not discovered.